//机器人的运动范围
class Solution {
public:
    int arr[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
    vector<vector<bool>>used;
    int count=0;
    int _m;
    int _n;
    int movingCount(int m, int n, int k) 
    {
        _m=m;
        _n=n;
        used.resize(m,vector<bool>(n,false));
        dfs(0,0,k);
        return count;
    }
    void dfs(int x,int y,int k)
    {
        count++;
        used[x][y]=true;
        for(int i=0;i<4;i++)
        {
            int nx=x+arr[i][0];
            int ny=y+arr[i][1];
            if(nx>=0 &&nx<_m &&ny>=0&&ny<_n &&!used[nx][ny] &&check(nx,ny,k))
            {
                dfs(nx,ny,k);
            }
        }
    }
    bool check(int x,int y,int k)
    {
        int count=0;
        while(x>0)
        {
            count+=x%10;
            x/=10;
        }
        while(y>0)
        {
            count+=y%10;
            y/=10;
        }
        return count<=k;
    }
};